package Algorithm.DoublePointer;

import java.util.Deque;
import java.util.LinkedList;

// https://leetcode.cn/problems/subarray-product-less-than-k/
public class Leetcode713_乘积小于k的子数组 {
    class Solution {
        public int numSubarrayProductLessThanK(int[] nums, int k) {
            // 自己写的时候，用了一个队列来保存
            Deque<Integer> stack = new LinkedList<>();
            int temp = 1;
            int result = 0;
            for (int i = 0; i < nums.length; i++){
                temp = temp * nums[i];
                stack.addLast(nums[i]);
                while(!stack.isEmpty() && temp >= k){
                    temp = temp / stack.pollFirst();
                }
                result = result + stack.size();
            }

            return result;
        }
    }

    // 上面的方法可以被双指针替换
    class Solution2 {
        public int numSubarrayProductLessThanK(int[] nums, int k) {
            int n = nums.length, ans = 0;
            if (k <= 1) return 0;
            for (int i = 0, j = 0, cur = 1; i < n; i++) {
                cur *= nums[i];
                while (cur >= k) cur /= nums[j++];
                ans += i - j + 1;
            }
            return ans;
        }
    }


}
